|
Bruun's algorithm is a fast Fourier transform (FFT) algorithm based on an unusual recursive polynomial-factorization approach, proposed for powers of two by G. Bruun in 1978 and generalized to arbitrary even composite sizes by H. Murakami in 1996. Because its operations involve only real coefficients until the last computation stage, it was initially proposed as a way to efficiently compute the discrete Fourier transform (DFT) of real data. Bruun's algorithm has not seen widespread use, however, as approaches based on the ordinary Cooley–Tukey FFT algorithm have been successfully adapted to real data with at least as much efficiency. Furthermore, there is evidence that Bruun's algorithm may be intrinsically less accurate than Cooley–Tukey in the face of finite numerical precision (Storn, 1993). Nevertheless, Bruun's algorithm illustrates an alternative algorithmic framework that can express both itself and the Cooley–Tukey algorithm, and thus provides an interesting perspective on FFTs that permits mixtures of the two algorithms and other generalizations. == A polynomial approach to the DFT == Recall that the DFT is defined by the formula: : For convenience, let us denote the ''N'' roots of unity by ω''N''''n'' (''n'' = 0, ..., ''N'' − 1): : and define the polynomial ''x''(''z'') whose coefficients are ''x''''n'': : The DFT can then be understood as a ''reduction'' of this polynomial; that is, ''X''''k'' is given by: : where mod denotes the polynomial remainder operation. The key to fast algorithms like Bruun's or Cooley–Tukey comes from the fact that one can perform this set of ''N'' remainder operations in recursive stages. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bruun's FFT algorithm」の詳細全文を読む スポンサード リンク
|